{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "toc-hr-collapsed": true,
    "toc-nb-collapsed": true
   },
   "source": [
    "###   实验三  链式结构线性表的实现\n",
    "####  建立一个单链表,实现基本操作:\n",
    "    1-分别使用正位序和逆位序的方法新建一个单链表\n",
    "    2-完成插入,删除,输出的操作\n",
    "    \n",
    "    \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "pycharm": {
     "is_executing": false
    }
   },
   "outputs": [],
   "source": [
    "class Node:\n",
    "    def __init__(self,initdata): # 节点初始化\n",
    "        self.data = initdata\n",
    "        self.next = None\n",
    "    def getData(self):   # 获得当前数据项\n",
    "        return self.data\n",
    "    def getNext(self):   # 获得后继数据项\n",
    "        return self.next\n",
    "    def setData(self,newdata):  # 设置数据项为newdata\n",
    "        self.data = newdata\n",
    "    def setNext(self,newnext):  # 设置next指针指向newnext\n",
    "        self.next = newnext\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "pycharm": {
     "is_executing": false
    }
   },
   "outputs": [],
   "source": [
    "class OrderedList:\n",
    "    def __init__(self): # 链表初始化\n",
    "        self.head = None\n",
    "    def add_正位序(self, item):  # 正位序添加元素的函数\n",
    "        current = self.head\n",
    "        previous = None\n",
    "        stop = False\n",
    "        while current != None and not stop:  # 从头遍历数据项,如果当前数据项大于加入的数据项,则停止遍历\n",
    "            if current.getData() > item:\n",
    "                stop = True\n",
    "            else:\n",
    "                previous = current\n",
    "                current = current.getNext()\n",
    "        temp = Node(item)    #   停止遍历后,生成节点,并将节点插入链表中\n",
    "        if previous == None:    #  当前节点为头节点\n",
    "            temp.setNext(self.head)   #  设置temp的next指针指向表头\n",
    "            self.head = temp   # 头指针指向temp节点,令temp为头节点\n",
    "        else:  # 如果当前节点不是头节点                \n",
    "            temp.setNext(current)    # 设置temp的next指针指向当前节点\n",
    "            previous.setNext(temp)   # 设置前驱节点的next指针指向temp\n",
    "            \n",
    "    def add_逆位序(self, item):\n",
    "        current = self.head\n",
    "        previous = None\n",
    "        stop = False\n",
    "        while current != None and not stop:\n",
    "            if current.getData() < item:   # 当前数据项小于加入的数据项,停止遍历\n",
    "                stop = True\n",
    "            else:\n",
    "                previous = current\n",
    "                current = current.getNext()\n",
    "        temp = Node(item)\n",
    "        if previous == None:\n",
    "            temp.setNext(self.head)\n",
    "            self.head = temp\n",
    "        else:\n",
    "            temp.setNext(current)\n",
    "            previous.setNext(temp)\n",
    "    \n",
    "    def print_list(self):   #  遍历并输出链表数据项\n",
    "        current = self.head\n",
    "        while current != None:\n",
    "            print(current.getData(), end=' ')\n",
    "            current = current.next\n",
    "        print(\"\\n\")\n",
    "\n",
    "    def showData_正位序(self):  #正位序遍历链表链表\n",
    "        print('正位序输入5个数:')\n",
    "        num = 0\n",
    "        inputList = []\n",
    "        while num<5:\n",
    "            item = int(input())\n",
    "            self.add_正位序(item)\n",
    "            num+=1\n",
    "            inputList.append(item)\n",
    "        print('正位序输入结果为:')\n",
    "        for i in inputList:\n",
    "            print(i,end = \" \")\n",
    "        print('\\n输出结果为:')\n",
    "        self.print_list()\n",
    "    \n",
    "    def showData_逆位序(self):\n",
    "        print('逆位序输入5个数:')\n",
    "        num = 0\n",
    "        inputList = []\n",
    "        while num<5:\n",
    "            item = int(input())\n",
    "            self.add_逆位序(item)\n",
    "            num+=1\n",
    "            inputList.append(item)\n",
    "        print('逆位序输入结果为:')\n",
    "        for i in inputList:\n",
    "            print(i,end = \" \")\n",
    "        print('\\n输出结果为:')\n",
    "        self.print_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "pycharm": {
     "is_executing": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "正位序输入5个数:\n",
      "正位序输入结果为:\n",
      "1 2 3 2 1 \n",
      "输出结果为:\n",
      "1 1 2 2 3 \n",
      "\n"
     ]
    }
   ],
   "source": [
    "mylist_正位序 = OrderedList()\n",
    "mylist_正位序.showData_正位序()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "pycharm": {
     "is_executing": false
    }
   },
   "outputs": [],
   "source": [
    "mylist_逆位序 = OrderedList()\n",
    "mylist_逆位序.showData_逆位序()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "xpython",
   "language": "python",
   "name": "xpython"
  },
  "language_info": {
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "version": "3.8.2"
  },
  "toc-autonumbering": false,
  "toc-showmarkdowntxt": true
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
